home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / libg_261.zip / libg_261 / libg++ / src / gen / MPlex.hP < prev    next >
Text File  |  1992-04-14  |  11KB  |  415 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /* 
  3. Copyright (C) 1988 Free Software Foundation
  4.     written by Doug Lea (dl@rocky.oswego.edu)
  5.     based on code by Marc Shapiro (shapiro@sor.inria.fr)
  6.  
  7. This file is part of the GNU C++ Library.  This library is free
  8. software; you can redistribute it and/or modify it under the terms of
  9. the GNU Library General Public License as published by the Free
  10. Software Foundation; either version 2 of the License, or (at your
  11. option) any later version.  This library is distributed in the hope
  12. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  13. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  14. PURPOSE.  See the GNU Library General Public License for more details.
  15. You should have received a copy of the GNU Library General Public
  16. License along with this library; if not, write to the Free Software
  17. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  18. */
  19.  
  20. #ifndef _<T>MPlex_h
  21. #ifdef __GNUG__
  22. #pragma interface
  23. #endif
  24. #define _<T>MPlex_h 1
  25.  
  26.  
  27. #include "<T>.Plex.h"
  28.  
  29.  
  30. // Number of bits per long, used in MChunk bit map operations
  31.  
  32. #define _MAP_BITS  32
  33.  
  34.  
  35. class <T>MChunk : public <T>IChunk
  36. {
  37. protected:
  38.  
  39.   unsigned long* map;          // bitmap of slots
  40.   int            unused;       // number of unused internal slots 
  41.  
  42.   void           mark(int);    // bitmap operations
  43.   void           free(int);
  44.   int            valid(int) const;
  45.  
  46. public:
  47.  
  48.                  <T>MChunk(<T>*    d,        // ptr to array of elements
  49.                         int      base_idx, // initial indices
  50.                         int      low_idx,  // & initially clear map
  51.                         int      fence_idx,
  52.                         int      top_idx);
  53.  
  54.                  ~<T>MChunk();
  55.  
  56. // virtuals
  57.  
  58.   int            first_index() const;
  59.   int            last_index() const;
  60.   int            succ(int idx) const;
  61.   int            pred(int idx) const;
  62.   <T>*           first_pointer() const;                 
  63.   <T>*           last_pointer() const;                 
  64.   <T>*           succ(<T>*) const;                 
  65.   <T>*           pred(<T>*) const; 
  66.   int            empty() const;
  67.   int            full() const;
  68.   int            valid_index(int i) const;
  69.   int            valid_pointer(const <T>* p) const;
  70.   <T>*           grow_high ();
  71.   <T>*           grow_low ();  
  72.   void           shrink_high ();
  73.   void           shrink_low ();     
  74.   void           clear(int);
  75.   void           cleardown(int);
  76.   int            OK() const;
  77.  
  78. // extensions
  79.  
  80.   int            unused_indices() const;   // how many free slot in low..fence?
  81.  
  82.   int            unused_index() const;     // return index of free slot
  83.  
  84.   int            del(int i);         // delete data indexed by i
  85.                                      // return true if was present
  86.   int            undel(int idx);     // un-delete data indexed by i
  87.                                      // return true if already present
  88.  
  89.   void           reset_low();        // reset low = lowest valid index; 
  90.   void           reset_high();       // same for high
  91.  
  92. };
  93.  
  94.  
  95. class <T>MPlex: public <T>Plex
  96. {
  97.   <T>MChunk*       ch;          // cached chunk
  98.   int              unused;      // # of free slots between low & fence
  99.  
  100.   void             make_initial_chunks(int up = 1);
  101.   void             cache(int idx) const;
  102.   void             cache(const <T>* p) const;
  103.   int              dopred(int) const;
  104.   int              dosucc(int) const;
  105.  
  106.   void             set_cache(const <T>MChunk* t) const; // logically, 
  107.                                                // not physically const
  108.  
  109. public:
  110.                    <T>MPlex();                 // set low = 0;
  111.                                                // fence = 0;
  112.                                                // csize = default
  113.  
  114.                    <T>MPlex(int ch_size);      // low = 0; 
  115.                                                // fence = 0;
  116.                                                // csize = ch_size
  117.  
  118.                    <T>MPlex(int lo,            // low = lo; 
  119.                             int ch_size);      // fence=lo
  120.                                                // csize = ch_size
  121.  
  122.                    <T>MPlex(int lo,            // low = lo
  123.                             int hi,            // fence = hi+1
  124.                             const <T&> initval,// fill with initval,
  125.                             int ch_size = 0);  // csize= ch_size
  126.                                                // or fence-lo if 0
  127.  
  128.                    <T>MPlex(const <T>MPlex&);
  129.  
  130.   void             operator= (const <T>MPlex&);
  131.  
  132. // virtuals 
  133.  
  134.   <T>&             high_element ();
  135.   <T>&             low_element ();
  136.   const <T>&       high_element () const;
  137.   const <T>&       low_element () const;
  138.  
  139.   Pix              first() const;
  140.   Pix              last() const ;
  141.   void             prev(Pix& ptr) const;
  142.   void             next(Pix& ptr) const;
  143.   int              owns(Pix p) const;
  144.   <T>&             operator () (Pix p);
  145.   const <T>&       operator () (Pix p) const;
  146.  
  147.   int              low() const; 
  148.   int              high() const;
  149.   int              valid(int idx) const;
  150.   void             prev(int& idx) const;
  151.   void             next(int& x) const;
  152.   <T>&             operator [] (int index);
  153.   const <T>&       operator [] (int index) const;
  154.     
  155.   int              Pix_to_index(Pix p) const;
  156.   Pix              index_to_Pix(int idx) const;
  157.  
  158.   int              can_add_high() const;
  159.   int              can_add_low() const;
  160.   int              full() const;
  161.  
  162.   int              add_high(const <T&> elem);
  163.   int              del_high ();
  164.   int              add_low (const <T&> elem);
  165.   int              del_low ();
  166.   void             clear();
  167.  
  168.   int              OK () const; 
  169.  
  170. // extensions
  171.  
  172.   int              count() const;             // # valid elements
  173.   int              available() const;         // # deleted elements
  174.  
  175.   int              unused_index()const;       // return index of a deleted elem
  176.   Pix              unused_Pix() const;        // return Pix of a deleted elem
  177.  
  178.   int              del_index(int idx);        // logically delete at idx;
  179.                                               // return true if was present
  180.   int              del_Pix(Pix p);            // delete at p
  181.  
  182.   void             undel_index(int idx);      // undelete at idx;
  183.   void             undel_Pix(Pix p);          // undelete at p;
  184.  
  185.   void             adjust_bounds();           // reset lo, hi to lowest &
  186.                                               // highest valid indices
  187.  
  188.   int              add(const <T&> elem);      // add anywhere
  189. };
  190.  
  191.  
  192. inline <T>MChunk:: ~<T>MChunk()
  193. {
  194.   delete map;
  195. }
  196.  
  197. inline void <T>MChunk::mark(int idx)
  198. {
  199.   unsigned int i = idx - base;
  200.   map[i / _MAP_BITS] |= 1 << (i & (_MAP_BITS - 1));
  201. }
  202.  
  203. inline void <T>MChunk::free(int idx)
  204. {
  205.   unsigned int i = idx - base;
  206.   map[i / _MAP_BITS] &= ~(1 << (i & (_MAP_BITS - 1)));
  207. }
  208.  
  209. inline int <T>MChunk::valid(int idx) const
  210. {
  211.   unsigned int i = idx - base;
  212.   return map[i / _MAP_BITS] & (1 << (i & (_MAP_BITS - 1)));
  213. }
  214.  
  215. inline  int <T>MChunk:: valid_index(int i) const
  216. {
  217.   return i >= low && i < fence && valid(i);
  218. }
  219.  
  220. inline  int  <T>MChunk:: valid_pointer(const <T>* p) const
  221. {
  222.   int i = ((int)p - (int)data) / sizeof(<T>);
  223.   return i >= 0 && i < (fence - base) &&
  224.     (map[(unsigned)i / _MAP_BITS] & (1 << (i & (_MAP_BITS - 1))));
  225. }
  226.  
  227. inline int <T>MChunk::empty() const
  228. {
  229.   return  fence - low - unused == 0;
  230. }
  231.  
  232. inline int <T>MChunk::full() const
  233. {
  234.   return  unused + (top - fence) + (low - base) == 0;
  235. }
  236.  
  237. inline int <T>MChunk::succ(int idx) const
  238. {
  239.   int i = (idx < low)? low : idx + 1;
  240.   while (i < fence && !valid(i)) ++i;
  241.   return i;
  242. }
  243.  
  244. inline int <T>MChunk::pred(int idx) const
  245. {
  246.   int i = (idx > fence)? (fence - 1) : idx - 1;
  247.   while (i >= low && !valid(i)) --i;
  248.   return i;
  249. }
  250.  
  251. inline int <T>MChunk::unused_indices() const
  252. {
  253.   return unused;
  254. }
  255.  
  256. inline <T>*   <T>MChunk:: grow_high ()
  257. {
  258.   if (!can_grow_high()) full_error();
  259.   mark(fence);
  260.   return &(data[fence++ - base]);
  261. }
  262.  
  263. inline <T>*   <T>MChunk:: grow_low ()
  264. {
  265.   if (!can_grow_low()) full_error();
  266.   mark(--low);
  267.   return &(data[low - base]);
  268. }
  269.  
  270. inline void <T>MChunk::reset_low()
  271. {
  272.   while (low < fence && !valid(low))
  273.   {
  274.     --unused;
  275.     ++low;
  276.   }
  277. }
  278.  
  279. inline void <T>MChunk::reset_high()
  280. {
  281.   while (fence > low && !valid(fence - 1))
  282.   {
  283.     --unused;
  284.     --fence;
  285.   }
  286. }
  287.  
  288. inline  int <T>MPlex::full () const
  289. {
  290.   return 0;
  291. }
  292.  
  293. inline int <T>MPlex::can_add_high() const
  294. {
  295.   return 1;
  296. }
  297.  
  298. inline int <T>MPlex::can_add_low() const
  299. {
  300.   return 1;
  301. }
  302.  
  303. inline int <T>MPlex::available() const
  304. {
  305.   return unused;
  306. }
  307.  
  308. inline int <T>MPlex::count() const
  309. {
  310.   return fnc - lo - unused;
  311. }
  312.  
  313. inline void <T>MPlex::set_cache(const <T>MChunk* t) const
  314. {
  315.   ((<T>MPlex*)(this))->ch = (<T>MChunk*)t;
  316. }
  317.  
  318. inline <T>& <T>MPlex:: operator [] (int idx)
  319. {
  320.   if (!ch-><T>MChunk::valid_index(idx)) cache(idx);
  321.   return * (ch->pointer_to(idx));
  322. }
  323.  
  324. inline const <T>& <T>MPlex:: operator [] (int idx) const
  325. {
  326.   if (!ch-><T>MChunk::valid_index(idx)) cache(idx);
  327.   return * ((const <T>*)(ch->pointer_to(idx)));
  328. }
  329.  
  330. inline  int <T>MPlex::Pix_to_index(Pix p) const
  331. {
  332.   if (!ch-><T>MChunk::valid_pointer((<T>*)p)) cache((<T>*)p);
  333.   return ch->index_of((<T>*)p);
  334. }
  335.  
  336. inline int <T>MPlex::high() const
  337. {
  338.   return (((const <T>MChunk*)tl())-><T>MChunk::valid_index(fnc-1)) ? 
  339.     fnc-1 : dopred(fnc-1);
  340. }
  341.  
  342. inline int <T>MPlex::low() const
  343. {
  344.   return (((const <T>MChunk*)hd)-><T>MChunk::valid_index(lo))? lo : dosucc(lo);
  345. }
  346.  
  347. inline  <T>& <T>MPlex::low_element ()
  348. {
  349.   return (*this)[low()];
  350. }
  351.  
  352. inline const <T>& <T>MPlex::low_element () const
  353. {
  354.   return (*this)[low()];
  355. }
  356.  
  357. inline  <T>& <T>MPlex::high_element ()
  358. {
  359.   return (*this)[high()];
  360. }
  361.  
  362. inline const <T>& <T>MPlex::high_element () const
  363. {
  364.   return (*this)[high()];
  365. }
  366.  
  367. inline  Pix <T>MPlex::index_to_Pix(int idx) const
  368. {
  369.   if (!ch-><T>MChunk::valid_index(idx)) cache(idx);
  370.   return Pix(ch->pointer_to(idx));
  371. }
  372.  
  373. inline void <T>MPlex::next(int& idx) const
  374. {
  375.   idx = (ch-><T>MChunk::valid_index(idx+1))? idx+1 : dosucc(idx);
  376. }
  377.  
  378. inline void <T>MPlex::prev(int& idx) const
  379. {
  380.   idx = (ch-><T>MChunk::valid_index(idx-1))? idx-1 : dopred(idx);
  381. }
  382.  
  383. inline Pix <T>MPlex::first() const
  384. {
  385.   return index_to_Pix(low());
  386. }
  387.  
  388. inline Pix <T>MPlex::last() const
  389. {
  390.   return index_to_Pix(high());
  391. }
  392.  
  393.  
  394. inline void <T>MPlex::undel_Pix(Pix p)
  395. {
  396.   undel_index(Pix_to_index(p));
  397. }
  398.  
  399. inline int <T>MPlex::del_Pix(Pix p)
  400. {
  401.   return del_index(Pix_to_index(p));
  402. }
  403.  
  404. inline <T>& <T>MPlex:: operator () (Pix p)
  405. {
  406.   return *((<T>*)p);
  407. }
  408.  
  409. inline const <T>& <T>MPlex:: operator () (Pix p) const
  410. {
  411.   return *((const <T>*)p);
  412. }
  413.  
  414. #endif
  415.